\chapter{Suy diễn chính xác: Loại trừ biến ngẫu nhiên}
Trong chương này, ta bàn về bài toán suy diễn trên mô hình đồ thị. Ta sẽ
thấy cấu trúc của đồ thị, bao gồm các quan hệ độc lập có điều kiện
và cách phân tích phân bố xác suất thành nhân tử tương ứng, là cực kì quan 
trọng để ta có tiến hành suy diễn trên các đồ thị phức tạp.

Tiêu điểm của chương này là kiểu truy xuất đồ thị quen thuộc nhất:
truy xuất xác suất có điều kiện, $P(\bm{Y}|\bm{E}=\bm{e})$ (xem phần \ref{sec:}).
Ta đã biết nhiều ví dụ của kiểu truy xuất này ở chương \ref{chapter:} và
chương \ref{chapter:}; như ta biết, có rất nhiều truy xuất hữu dụng kiểu này,
bao gồm giải thích, tiên đoán, suy luận nguyên nhân, và rất nhiều kiểu khác nữa.

Theo định nghĩa xác suất có điều kiện, ta biết rằng

\Eqn{
P(\bm{Y}|\bm{E}=\bm{e}) &= \frac{P(\bm{Y},\bm{e})}{P(\bm{e})}
}
Tử số $P(\bm{y},\bm{e})$ có thể tính bằng cách cộng tất cả các xác suất của
các phép gán cho $\Cal{X}$ phù hợp với $\bm{y}, \bm{e}$. Chính xác hơn, đặt $\bm{W}=\Cal{X}-\bm{Y}-\bm{E}$
là các biến ngẫu nhiên không nằm trong truy xuất $\bm{Y}$ cũng như bằng chứng $\bm{E}$.
Ta có

\Eqn{\label{eq:ch9_numerator}
P(\bm{y},\bm{e}) = \sum_{\bm{w}} P(\bm{y},\bm{e},\bm{w})
}
Do $\bm{Y},\bm{E},\bm{W}$ bao gồm tất cả các biến của mô hình nên mỗi số hạng
$P(\bm{y},\bm{e},\bm{w})$ trong tổng trên đơn giản là một phần tử của xác suất
chung của $\Cal{X}$.

Xác xuất của bằng chứng $P(\bm{e}$ cũng có thể tính như trên. Tuy nhiên, ta có
thể tính như sau

\Eqn{\label{eq:ch9_evidence}
P(\bm{e}) = \sum_{\bm{y}} P(\bm{y},\bm{e})
}
và lợi dụng được các tính toán trong công thức \eqref{eq:ch9_numerator}. Nếu
ta tính cả hai công thức \eqref{eq:ch9_numerator} và công thức \eqref{eq:ch9_evidence},
ta có thể chia $P(\bm{y},\bm{e})$ cho $P(\bm{e})$ để được xác suất cần tính
$P(\bm{y}|\bm{e})$. Để ý rằng các bước này tương đương với việc tính 
$P(\bm{y}^k|\bm{e}), \forall\bm{y}^k\in \bm{Y}$ và chuẩn hóa chúng sao cho tổng
của chúng bằng $1$.

\section{Độ phức tạp thuật toán}
Về nguyên tắc, mô hình đồ thị có thể trả lời mọi kiểu truy xuất kể trên. Ta chỉ cần
tính xác suất, cộng chúng lại (trong trường hợp tính xác suất có điều kiện), tìm
xác suất lớn nhất (trong trường hợp truy xuất MAP), hoặc cả hai (trong trường hợp
truy xuất MAP không đầy đủ). Tuy nhiên, cách tiếp cận bài toán suy diễn này không
thỏa mãn được chúng ta vì nó đem lại lượng tính toán xác suất bùng nổ theo cấp số nhân mà
mô hình đồ thị vốn được thiết kế để tránh.

Tuy nhiên, ta sẽ thấy \textbf{bùng nổ cấp số nhân trong bài toán suy diễn (gần như chắc chắn)
không thể tránh khỏi trong trường hợp xấu nhất: Bài toán suy diễn trong mô hình đồ
thị là bài toán $\Cal{NP}$-khó, và vì thế có thể bài toán này cần thời gian
cấp số nhân trong trường hợp xấu nhất (trừ khi $\Cal{P}=\Cal{NP}$). Hơn nữa, suy
diễn gần đúng cũng là bài toán $\Cal{NP}$-khó. May mắn là, câu chuyện không dừng
ở những kết quả xấu này. Nói chung, ta thường không để ý đến trường hợp xấu nhất mà
đến các trường hợp ta gặp trong thực tế. Trong phần còn lại của cuốn sách này, ta có 
thể thực hiện nhiều ứng dụng thực tế một cách rất hiệu quả sử dụng suy diễn chính
xác cũng như suy diễn gần đúng trong mô hình đồ thị.}

Khi phân tích độ phức tạp thuật toán, ta sẽ tập trung vào vào mạng Bayes. Do
mạng Bayes có thể biểu diễn bằng mạng Markov mà không làm tăng kích cỡ mạng,
mọi chứng minh độ khó của bài toán suy diễn trên mạng Bayes cũng đúng với
độ khó của bài toán suy diễn trên mạng Markov.

\subsection{Suy diễn chính xác}
\subsection{Suy diễn gần đúng}